#include <vector>
using namespace std;
/*
 * @lc app=leetcode.cn id=130 lang=cpp
 *
 * [130] 被围绕的区域
 */

// @lc code=start
int dxdy[][4] = {
    {0, 0, 1, -1},
    {1, -1, 0, 0}
};

class Solution {
public:

    
    void solve(vector<vector<char>>& board) {
        for (int i = 0; i < board[0].size(); i++) {
            if (board[0][i] == 'O') dfs(0, i, board);
        }
        for (int i = 1; i < board.size() - 1; i++) {
            if (board[i][0] == 'O') dfs(i, 0, board);
            if (board[i][board[0].size() - 1] == 'O') dfs(i, board[0].size() - 1, board);
        }
        for (int i = 0; i < board[0].size(); i++) {
            if (board[board.size() - 1][i] == 'O') dfs(board.size() - 1, i, board);
        }

        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] == '-') board[i][j] = 'O';
                else if (board[i][j] == 'O') board[i][j] = 'X';
            }
        }
    }

    void dfs(int x, int y, vector<vector<char>> & board) {
        board[x][y] = '-';
        for (int i = 0; i < 4; i++) {
            int nx = x + dxdy[0][i], ny = y + dxdy[1][i];
            if (nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size() && board[nx][ny] == 'O') {
                dfs(nx, ny, board);
            }
        }
    }
};
// @lc code=end

